package com.yinxin.wudasuanfa.dongtaiguihua;

import java.util.Arrays;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 回溯算法
 * 给定一个包含大写字母和小写字母的字符串，
 * 找到通过这些字母构造成的最长的回文串。
 * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
 * @date 2022/5/617:24
 */
public class Exercise5 {
    public static void main(String[] args) {
       int ans = longestPalindrome("abccccdd");
       System.out.println("最长回文串长度为："+ans);
    }

    public static int longestPalindrome(String s) {
        int[] count = new int[128];
        //记录下每个字符出现的次数
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
           System.out.println(Character.getNumericValue(c));
            count[c]++;
        }
        int ans = 0;
        for (int v : count) {
            //这个小技巧可以使 偶数不变，奇数-1
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {//v%2==1表示这个对应索引的索引就是对应字母的char类型，ans % 2 == 0表示这个ans可以被2整除也就是4、6、8
                ans++;
            }
        }
        return ans;
    }

}
